[프로그래머스] 여행경로

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 “ICN” 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

tickets	return
[[“ICN”, “JFK”], [“HND”, “IAD”], [“JFK”, “HND”]]	[“ICN”, “JFK”, “HND”, “IAD”]
[[“ICN”, “SFO”], [“ICN”, “ATL”], [“SFO”, “ATL”], [“ATL”, “ICN”], [“ATL”,”SFO”]]	[“ICN”, “ATL”, “ICN”, “SFO”, “ATL”, “SFO”]

저는 공항과 티켓을 클래스로 생성해서 해결했습니다.

따로 클래스를 생성하지 않고 해결하시는 분들도 많으시더라구요! 저도 그 방법으로 다시 풀어보긴 했지만 먼저 사용했던 방법이 뭔가 정점 - 간선의 관계를 객체지향으로 잘 표현한 것 같아 제 입장에선 이해가 더 쉬웠던 거 같아요!

그래서 전 클래스를 생성해 해결한 방법을 포스팅했습니다.

우선 알파벳 순서로 정렬하는 과정은 두 가지 타이밍이 있습니다.

저는 첫 번째 타이밍에 정렬을 수행했습니다. 이 경우 DFS를 돌며 최종적으로 나온 루트가 자동적으로 정렬된 루트가 되며 여러 개의 루트를 저장할 필요 없이, 최초로 생성된 루트를 채택하면 됩니다.

두 번째 방법으로 정렬하는 것은 가짓수가 적어질 수 있어 더 효율적일 수 있으나 모든 루트를 저장 후, 마지막에 정렬해야 해서 루트를 저장하는 자료형에 있어 한정적일 수 있습니다.

DFS를 수행하며 여행 경로대로 저장된 String 배열을 리턴합니다.

Method	Return	Description
solution(String[][] tickets)	String[]	최초 티켓 정보를 입력 받아 여행 경로를 담은 String 배열을 반환
DFS(int N, Airport begin)	String[]	티켓 개수(N)와 출발지점을 입력 받아 rDFS를 호출합니다.
rDFS(int N, int cnt, Airport begin, String[] visited)	int	DFS를 수행하는 재귀 함수로, 입력 받은 visited 배열에 저장합니다.

rDFS의 cnt는 저장된 여행지 개수이며, 모든 티켓을 사용하면 N+1이 됩니다. cnt 값을 유지하기 위해 cnt 값을 return해 줍니다.

사용 연어: Java

감사합니다.

Text by Chaelin. Photographs by Chaelin, Unsplash.

[프로그래머스] 여행경로 Success